package question.solution47;

import question.SolutionTemplate;

import java.util.*;

public class Solution47 implements SolutionTemplate {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> numList = new ArrayList<>();
        for(int num : nums){
            numList.add(num);
        }
        List<List<Integer>> result = new ArrayList<>();
        permute(numList, new ArrayList<>(), result);
        return result;
    }
    private void permute(List<Integer> restNums, List<Integer> singleResult, List<List<Integer>> result){
        Set<Integer> existNums = new HashSet<>();
        for(int i=0;i<restNums.size();i++){
            int e = restNums.get(i);
            if(restNums.size() == 1){
                singleResult.add(e);
                result.add(copySingleResult(singleResult));
                singleResult.remove(singleResult.size()-1);
                return;
            }
            if (existNums.contains(e)){
                continue;
            }
            existNums.add(e);
            singleResult.add(e);
            restNums.remove(i);

            permute(restNums, singleResult, result);

            singleResult.remove(singleResult.size()-1);
            restNums.add(i, e);
        }
    }

    private List<Integer> copySingleResult(List<Integer> singleResult){
        List<Integer> r = new ArrayList<>();
        for(Integer e : singleResult){
            r.add(e);
        }
        return r;
    }

    public void test() {
        int[] nums = {1,2,3};
        List<List<Integer>> result = permuteUnique(nums);
        return;
    }
}
